package com.study.algorithm.niuke.practice;

/**
 * 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1）
 * ，每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？
 * 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 *
 * 我的做法完全是一步一步尝试，得出结果
 *
 * 通过理论得出的做法：
 * 下面是f(x)的导数：
 *
 * 乘积函数在n/m=e的时候，取得最大值,可知，当x∈(0,e)时f(x)单调递增，当x>e时，单调递减，因此，在x=e时取得最大值，e≈2.718,是自然对数。
 * 从函数图像上也可以看出这一点
 * f(x)的函数图像
 * 又因为x的取值只能为整数，且f(3)>f(2)，所以，当n＞3时，将n尽可能地分割为3的和时，乘积最大。 当n＞3时，有三种情况，即n%3==0, n%3==1, n%3==2,如下所示
 * 上式中除法向下取整
 * 当n≤3时，只有
 * 当n==2时f(x)=1；
 * 当n==3时f(x)=2;
 *
 *
 */
public class CutRope {

    public int cutRope(int target) {
        if (target <= 2) {
            return 1;
        }
        int rope = 2;
        int maxResult = 0;
        int currSelectedRope = rope;
        double tempRope = Math.sqrt(target);
        int temp1 = (int) tempRope;
        int maxRope = tempRope > temp1 ? temp1 + 1 : temp1;
        for (; rope <= maxRope; rope++) {
            int currMaxResult = mutiRope(rope, target);
            boolean isBigger = currMaxResult > maxResult;
            maxResult = isBigger ? currMaxResult : maxResult;
            currSelectedRope = isBigger ? rope : currSelectedRope;
        }
        return maxResult;
    }


    private int mutiRope(int rope, int target) {
        int result = 1;
        if (rope == 1) {
            result = target < 1 ? result : target;
            return result;
        }
        int ropeMiniVal = target / 2;
        int ropeMaxVal = target - ropeMiniVal;
        if (rope == 2) {
            return ropeMaxVal * ropeMiniVal;
        }
        int miniRope = rope / 2;
        int maxRope = rope - miniRope;
        return mutiRope(miniRope, ropeMiniVal) * mutiRope(maxRope, ropeMaxVal);
    }
}
